// mark
/*6.48 已知在二叉树中，*root为根结点，*p和*q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。。*/
#include <stdio.h>
#include <stdlib.h>
#include "E:\Desktop\data_struct\5TREE\1_bin_tree\creat.h"

tree *stack[100];
int top;
tree *fun_6_48_1(tree *root, int key)
{
    int flag[100] = {0};
    int find = 0;
    stack[++top] = root;
    while (top >= 0)
    {
        tree *p = stack[top];
        if (p->data == key)
            break;
        switch (flag[top])
        {
        case 0:
            flag[top]++;
            if (p->left)
            {
                stack[++top] = p->left;
            }
            break;
        case 1:
            flag[top]++;
            if (p->right)
            {
                stack[++top] = p->right;
            }
            break;
        case 2:
            flag[top] = 0;
            top--;
            break;

        default:
            break;
        }
    }
}
tree *fun_6_48(tree *root, int key1, int key2)
{
    // 1.location
    tree *p, *q;
    top = -1;
    p = fun_6_48_1(root, key1);
    tree *path1[100];
    int i = 0;
    while (i <= top)
    {
        path1[i] = stack[i];
        i++;
    }
    top = -1;
    q = fun_6_48_1(root, key2);
    tree *path2[100];
    int j = 0;
    while (j <= top)
    {
        path2[j] = stack[j];
        j++;
    }
    int k = 0;
    // 任意两点必有一个祖先是根节点
    while (path1[k] == path2[k])
        k++;
    printf("%3d", path1[k - 1]->data);
    return path1[k - 1];
}

int main()
{
    /*******************code*******************/
    int n = 15;
    int a1[15] = {1,
                  2, 3,
                  4, 5, NULL, 6,
                  NULL, 7, 8, NULL, NULL, NULL, NULL, 9};
    tree *root;
    CreatTree(root, a1, n, 0);
    fun_6_48(root, 5, 8);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
